public class 排序数组 {

    // 归并
    public int[] tmp;
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        emergeSort(nums,0,nums.length - 1);
        return nums;
    }
    public void emergeSort(int[] nums,int left,int right){
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        emergeSort(nums,left,mid);
        emergeSort(nums,mid + 1,right);
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] < nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }
        for (int j = left;j <= right;j++) {
            nums[j] = tmp[j - left];
        }
    }
}
